/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-17
 * Time: 9:57
 */
class Node {
     public int data;
     public Node next;//下一节点的指针
     public Node(int data) {
        this.data=data;
    }
}
public class MySingleLinkedList {
       public Node head;//头结点
    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);//要插入的节点
        if(this.head==null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }
    }
    //打印单链表
    public void display() {
        Node cur =this.head;
        while(cur!=null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //尾插法
    public void addLast(int data) {
        Node node =new Node(data);
        if(this.head==null) {
            this.head=node;
        }else {
            //先找到尾
            Node cur = this.head;
            while(cur.next!=null) {
                cur = cur.next;
            }
            cur.next =node;
        }
    }
    //查找关键字是否在单链表中  如果在返回true  如果不在返回false
    public boolean contains(int key) {
        Node cur = this.head;
        while(cur!=null) {
            if(cur.data==key) {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //链表中元素的个数
    public int size() {
        Node cur =this.head;
        int count =0;
        while(cur!=null) {
            count++;
            cur= cur.next;
        }
        return count;
    }
    private void checkIndex(int index) {
        if(index<0||index>=size()) {
            throw new RuntimeException("你输入的坐标index不合法: >");
        }
    }
    private Node searchIndex(int index) {
        Node cur =head;
        //先让cur走index-1步 就到达index前一个位置
        while((index-1)!=0) {
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入元素  index 代表下标  从下标0开始
    public void addIndex(int index,int data) {
        Node node =new Node(data);
        //判断index 合不合法
        checkIndex(index);
        if(index == 0) {
            //相当于头插
            addFirst(data);
            return;
        } else if(index==size()-1) {
            //相当于尾插
            addLast(data);
            return;
        } else {
            //找到index的前一个
            Node cur = searchIndex(index);
            node.next =cur.next;
            cur.next =node;
        }
    }
    private Node searchKey(int key) {
        Node cur = head;
        while(cur.next.data!=key) {
            cur = cur.next;
        }
        return cur;
    }
    //删除第一次出现关键字的点
    public void remove(int key) {
        if(this.head.data==key) {
            this.head =this.head.next;
            return;
        }
        //找到key的前一个
        Node prev =searchKey(key);
        Node cur =prev.next;
        prev.next =cur.next;
    }
    //删除所有关键字key
    public void removeAllKey(int key) {
        Node prev =head;
        Node cur = prev.next;
        while(cur!=null) {
            if(cur!=null&&cur.data==key) {
                while(cur!=null&&cur.data==key) {
                    cur=cur.next;
                }
                prev.next = cur;
            }else {
                prev =cur;
                cur=cur.next;
            }
        }
        if(this.head.data==key) {
            this.head=this.head.next;
        }
    }

//    class Solution {
//        public boolean isValid(String s) {
//            if(s.length()%2!=0) {
//                return false;//如果不是偶数那必然有一个括号落单
//            }
//            //创建一个栈
//            Stack<Character> stack =new Stack<Character>();
//            //将字符串转换成字符数组的形式
//            char charArray[] = s.toCharArray();
//            for(int i=0;i<charArray.length;i++) {
//                char c = charArray[i];
//                if(c=='(') {
//                    stack.push('(');
//                }else if(c=='[') {
//                    stack.push('[');
//                }else if(c=='{'){
//                    stack.push('{');
//                }else {
//                    //如果刚开始就是右边括号
//                    if(stack.isEmpty()) return false;
//                    //否则的话就已经有左括号压入栈底  然后与右括号比较
//                    char top = stack.peek();//取出栈顶元素与其比较
//                    if(top=='('&&c==')'||top=='['&&c==']'||top=='{'&&c=='}') {
//                        //弹出元素比较下一对
//                        stack.pop();
//                    }else {
//                        //如果与之不匹配那就false
//                        return false;
//                    }
//                }
//            }
//            //最后判断栈是否为空  如果为空那就证明所有的都匹配成功  否者不匹配
//            return stack.isEmpty();
//        }
//    }

//
//    public int minArray(int[] numbers) {
//        int left =0;
//        int right = numbers.length -1;
//        while(left<right) {
//            int mid = (left+right)>>1;
//            if(numbers[mid] > numbers[right]) {//异常情况  正常应该是中间值<右边
//                left = mid+1;
//            }else if(numbers[mid]<numbers[right]){
//                right =mid;
//            }else {
//                return findMin(numbers,left,right);
//            }
//        }
//        return numbers[left];
//    }
//    public int findMin(int[] numbers,int left,int right) {
//        int result = numbers[left];
//        for(int i=left ;i<=right;++i) {
//            if(numbers[i]<result) {
//                result= numbers[i];
//            }
//        }
//        return result;
//    }



}

